package com.leetcode.BinaryTree;

//二叉树的最近公共祖先
public class lc_236 {
    public static void main(String[] args) {

    }
    /**
     * 寻找二叉树中两个节点的最近公共祖先(LCA)
     * 判断是否新建方法：
     * 该方法已经是一个完整独立的解决方案，不需要新建其他辅助方法。
     * 递归过程可以直接使用原方法，因为每次递归处理的都是相同的子问题（在子树中查找LCA）。
     * 传入传出参数也保持一致，不需要额外参数。
     *
     * @param root 当前子树根节点
     * @param p 要查找的第一个节点
     * @param q 要查找的第二个节点
     * @return 返回p和q的最近公共祖先节点，如果不存在则返回null
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 边界条件：
        // 1. 如果当前节点为null，说明到达叶子节点的子节点，返回null
        // 2. 如果当前节点就是p或q，说明找到了其中一个节点，直接返回当前节点
        // 这两种情况都不需要继续向下搜索
        if(root == null || root == p || root == q) return root;

        // 递归处理左子树：在左子树中查找p或q
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        // 递归处理右子树：在右子树中查找p或q
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        // 后序遍历处理逻辑：
        //1. 如果左右子树都没有找到,说明太深了,直接返回null
        if(left == null && right == null){
            return null;
        }
        // 2. 如果左子树返回null，右子树肯定不为null, 返回右子树的结果
        if(left == null) return right;
        // 3. 如果右子树返回null，左子树肯定不为null, 返回左子树的结果
        if(right == null) return left;
        // 4. 如果左右子树都不为null，说明当前节点就是分叉点（即LCA），返回当前节点
        return root;
    }
}
